此系列为Cousera上Standford的Mining Massive Datasets课程学习笔记。 这是该系列的第二篇笔记：Link Analysis and PageRank
链接分析 Link Analysis
图类数据 Graph Data
图由一组节点和一组边组成，根据边有没有方向可以分为有向图和无向图。
社交网络可以用图来描述、媒体网络可以用图来描述、信息网络也可以用图来描述、互联网更可以用图来描述！ 
Web也可以看作一张图。
Web as a Graph
- Web 可以看作一个有向图
- 节点： 网页
- 边 ： 超链接
Web网络图举例：
How to organize the Web?
早些时候，互联网刚起步的时代，人们手动组织网页目录(Web directories)，像雅虎、DMOZ等。
现在都是采用网页搜索(Web Search)的形式，信息检索办法: 在一个小的、可信任的页面集合中寻找相关的网页。
但是， Web非常大，林子大了什么鸟都有，充满不可信任的的网页、奇怪的东西、垃圾邮件等。
做Web搜索有两大挑战： 1. 该信任哪些网页？ 2. 什么是最好结果？
对于第一点，可以认为可信任的页面里的链接一般都互相指向，这样就可以确定大部分的可信任网页，但并不是绝对的。 对于第二点，在搜索引擎上搜索的绝大部分都是没有最好的答案的，怎么提供用户最想要的答案是个问题。
Ranking Nodes on the Graph
不是所有网页都一样“重要“！ 比如：https://www.baidu.com/ vs http://www.liuhe.website/ 很容易判断熟轻熟重。
在Web这个图里，每个节点相连的边数差异很大！
链接分析算法简介： 
PageRank
The "Flow" Formulation
计算节点（网页）权重的想法：把链接当作权重（Links as votes）
基本想法是这样的，如果一个网页很重要，那么指向它和它指向别的网页的链接应该很多。有一个问题就是考虑指向它的链接还是它指出去的链接呢？
如果考虑指出去的链接的话，那只要大家都在自己的网页上放一大堆链接就可以提高PageRank了，这样并不能反应一个网站的重要程度，所以我们考虑指向该网页的链接。
那么还有一个问题，是不是所有指向你的链接都一样重要？？ 显然不是！ 如果Google首页有指向你的链接，你的流量很可能就会爆增，但是我的首页如果加上指向你的链接可能并不会带来什么流量。
所以每个链接带来的权重是不一样的，来自重要的网站的链接权重应该更高些。
一个例子： 
简单的递归公式
每个链接的权重与其源网站的重要程度成比例。
设页面 \(j\) 的权重为 \(r_j\) ，该页有 \(n\) 个指向其他页面的链接，那么，每个链接给那个网站带来的权重为 $ r_j / n $ 。
页面 \(j\) 自己的权重来自所有指向它的链接的权重之和。
很简单吧？这就是"Flow"模型。
我们尝试解一下上图中的方程组，即： $ r_y = r_y / 2 + r_a / 2 $ $ r_a = r_y / 2 + r_m $ $ r_m = r_a / 2 $
发现解并不唯一，只能解得两两之间的关系，原因在于方程组里没有常数，我们还需要加一个条件： $ r_y + r_a + r_m = 1 $
这样解得：$ r_y = , r_a = , r_m = $
像这种小规模例子我们可以直接用高斯消元法球解，但是像web这么大的图肯定不可能人工求解，我们需要一个更好的计算方法。
Matrix Formulation
警告：以下内容会涉及线性代数以及概率论。
我们用邻接矩阵 \(M\) 来表示图，设页面 \(i\) 有 $ d_i $ 个外链，如果 $ i -> j $ ，那么 $ M_{ji} = $ 否则 $ M_{ji} = 0 $ 其中 \(M\) 是一个列随机矩阵，每列的和等于1.
我们再用一个向量 \(r\) 来表示所有页面的PageRank，$ r_i $ 是页面 \(i\) 的得分，并且 $ _i r_i = 1 $
现在，上节的方程($ r_j = _{i j} $)就可以该写成： $ = M $
用个例子解释一下： 假设页面 \(i\) 链向3个页面，包括 \(j\) ，如图所示： 
矩阵乘法是这样的，结果矩阵的 \([i, j]\) 元素是 $A_{i0} * B_{0j} + A_{i1} * B_{1i} + ... + A_{in} * B_{nj} $ 得到的。 
所以 \(M\) 在与 $r $ 相乘的结果也是一个列向量，这个列向量第 \(i\) 个元素的值就等于矩阵 \(M\) 的第 \(j\) 行乘以 \(\vec r\) ，数学表达式就是 $ r_j = {k=0}^{n} M{jk}*r_i $，由邻接矩阵所表示的意义可知，这与之前的Flow Equation是等效的。
一个例子： 
特征向量公式
我们先来复习一下什么是特征值(eigenvalue)和特征向量(eigenvector)。
如果表达式：$ A x = x $ 成立，则称\(\vec x\)为矩阵\(A\)的特征向量， \(\lambda\)为矩阵\(A\)的特征值，其中 \(\vec x\)是任意向量， \(\lambda\)是常数。
之前得到的矩阵公式为：\(\vec r = M \cdot \vec r\)，正好是符合上述表达式，矩阵\(M\)的特征向量就是\(\vec r\)，特征值就是\(1\)。
有了这个重大发现之后就可以高效的计算 \(\vec r\) 了，我们管这个方法叫幂迭代(Power iteration)
幂迭代 Power Iteration
幂迭代 * 假设有N个web页面 * 初始化：$ r^{(0)} = [1/N, .... 1/N]^T $ * 迭代：$ r^{(t+1)} = M r^{(t)} $ * 终止条件：$ |r{(t+1)}-r{(t)}|_1 < $ * 其中 $ |x|_1 = _{i=1}^{N}|x_i| $
看了这个之后是不是觉得很好实现？就是一个while循环而已。 还是那个例子： 
经过n轮迭代之后，\(\vec r\) 的值稳定在$ [6/15, 6/15, 3/15]^T$ ，与之前解方程组的结果一致。
Random Walk Interpretation
现在我们知道PageRank怎么高效的计算了，那么怎么理解这个网页的“重要“程度这个数值的具体意思呢？这里提供了一种解释：随机漫游解释。
假设有一个漫步者随机地在网页中漫游： * 在 \(t\) 时刻，这个人在某个页面 \(i\) * 在 \(t+1\) 时刻，漫步者从页面 \(i\) 的链接中随机选了一条 * 经由那个链接到达了 \(j\) 页面 * 无限重复这一过程
我们再令一个向量 \(p(t)\)，它的第 \(i\) 个值即\(p_i(t)\)表示在 \(t\) 时刻这个漫步者在页面 \(i\) 的概率。 所以 \(p(t)\) 表示所有页面的概率分布。
那么漫步者在 \(t+1\) 时刻在哪？ 由于选择每个链接是随机的，所以 \(t+1\) 时刻漫步者在当前页面指向的每个页面的概率都相等，都等于当前页面的出度分之一，所以有： $ p(t+1) = M p(t) $ 可见这和PageRank的方程是一样的。
设漫步者会达到一个稳态： $ p(t+1) = M p(t) = p(t) $ 在这个稳态，漫步者在以后任何时刻出现在某个页面的概率都相等，这时 \(p(t)\) 是一个平稳分布(stationary distribution)。
所以结论就是： * \(\vec r\) 的值是随机漫步的平稳分布 * 一个网页的PageRank得分代表了一个随机漫步者在无限的漫步过程中在某个时间 \(t\) 出现在这个页面的概率！
存在性和唯一性
这个随机漫步过程是一个马尔科夫过程 所以有： > 对于满足一定条件的图，其平稳分布是唯一的，并且终将会达到平稳分布无论在 \(t=0\) 时刻的概率初始值是什么。
The Google Formulation
上面说要满足一定条件，其平稳分布才会唯一并且无论初始值是什么，接下来就要探讨这一定条件是什么。
首先来看三个问题：
$ r_j^{(t+1)} = _{i j} $ 或者 $ r = M r $
- 这个东西（\(\vec r\)）是否收敛？
- 这个东西是否收敛到我们期待的结果？
- 得到的结果是否有意义？
我们一个一个回答。
Does this converge?
蜘蛛陷阱(Spider trap)：
假设图中只有两个节点A和B，如图所示： 
初始化 $ r_a = 1, r_b = 0 $，按照公式迭代，我们得到一下结果： 
0和1不断反转，不会收敛。再来看下一个问题。
Does it converge to what we want?
死胡同问题(Dead end problem)：
假设图中只有两个节点a和b，如图所示： 
初始化 $ r_a = 1, r_b = 0 $，代入公式迭代得到以下结果： 
最终收敛到0，这显然不是我们想要的。
两个问题总结一下： 
Problem : Spider Traps
假设有图： 
其邻接矩阵 \(M\) 为： 
带入公式迭代，结果为： 
最终，\(r_m = 1\) 而 $r_y = r_a = 0 $ 。这从漫步者的角度很好理解，在经过一段时间之后，漫步者到达了 \(m\) 节点，然而 \(m\) 节点只有指向自己的链接，然后就只能一直停留在 \(m\) ，所以最后的概率一定是1, 而其他两个节点的概率就变成了0 。
解决方案
随机传送 Random Teleports
Google解决这个问题的办法是：到达某个节点后 * 有 \(\beta\) 的概率随机找一个链接过去 * 剩下 \(1-\beta\) 的概率跳到一个随机的页面 * 一般 \(\beta\) 的值在 \(0.8\) 到 \(0.9\) 之间
这样就使得漫步者在到达m节点之后有一定的概率跳出去！ 
Problem : Dead Ends
假设有图： 
其邻接矩阵为： 
由于m节点没有链接到其他界面，所以m的那一列都等于零。 代入公式迭代，得到结果： 
漫步者到达m之后发现是死胡同，无路可走了，然而他也不会在m停留，所以最后出现在三个节点的概率都等于0 。
解决方案
依旧是传送！
当漫步者到达死胡同时，传送的概率变为 \(1.0\) ，随机传送到任意页面，然后图就变成了如下： 
邻接矩阵变为： 
这样问题就解决了，漫步这每次到m之后，发现去所有页面的概率都相同且不为零，相当于随机跳转到一个页面。
为什么传送可以解决这些问题？
我们知道求解PageRank的过程实际上是一个马尔科夫过程，也叫马尔科夫链。
马尔科夫链(Markov chains)： * 拥有一组状态 \(X\) * 转移矩阵 \(P\) ，且 \(P_{ij} = P(X_t=i | X_{t-1} = j)\)，\(P_{ij}\) 的意思就是已知上一步在 \(j\)，现在这步在 \(i\) 的概率 * \(\pi\) 是每个状态 \(x\) 特定的平稳分布 * 目标就是找到 \(\pi\) 使得 \(\pi = P \pi\)
条件： 对于任意的初始向量，只要马尔科夫转移矩阵 \(P\) 满足随机的(stochastic)，不可约的(irreducible)和非周期的(aperiodic)，那么对矩阵 \(P\) 应用幂迭代就一定会收敛到一个不变的向量。
我们来讨论一下为什么随机传送可以让矩阵 \(M\) 满足上述条件。
Make M Stochastic
随机(Stochastic)的意思就是每列的和加起来等于\(1\)
我们知道下面的图会造成死胡同问题(Dead End)： 如果让其在没有出度的节点可以随机跳转到任意节点的话就相当与在 \(m\) 节点上新加了几条边： 
这样 \(m\) 的出度就变成了3，矩阵 \(M\) 也变成了： 
现在 \(M\) 矩阵就满足了随机性，每列的和都等于 \(1\)。
我们把新矩阵记做 \(A\)，有如下计算公式： > $ A = M + a^T(e) $
如果节点 \(i\) 没有出度则 \(a_i=1\)，否则 \(a_i=0\) ; $ e$ 是单位行向量。
Make M Aperiodic
周期性(periodic)定义：如果存在一个 $k>1 $ 使得两次到达同一个状态的间隔总是 \(k\) 的整数倍，那么这条链就是具有周期性的。
上图就是一个具有周期性的链，每隔两步就会回到同一状态。 加上随机传送就变成了： 
这样不论每隔多少步也不一定会回到同一状态，即不具有周期性。
Make M Irreducible
不可约(Irreducible)的意思是：对于任何状态，都有从这个状态跳到任意另一个状态的可能性。
如图，其中绿色的线是加上随机跳转之后： 
Random Jumps
从前面的分析可知，随机跳转可以是 \(M\) 满足随机、非周期和不可约的性质，这就是Google的解决方案。
- 在每一步，漫步者有两个选择：
- \(\beta\) 的可能性随机选一个链接
- \(1-\beta\) 的可能性跳转到随机页面
PageRank 计算方程 就变成了： > $ r_j = _{i j} + (1-) $
其中 \(\sum _{i \to j} \beta \frac{r_i}{d_i}\) 是具有 \(\beta\) 的概率随机选择一个链接，\((1-\beta)\frac{1}{n}\) 是 \(1-\beta\) 的概率跳转到随机页面，其中 \(n\) 是图中节点个数。
我们还打算用幂迭代方法计算PageRank，所以还需要变成矩阵形式。
The Google Matrix A > $ A = M + (1 - ) e e^T $
What is \(\beta\) ? 实践表明 \(\beta\) 取在 $0.8 $~ \(0.9\) 之间较好，其中 \(\beta=0.85\) 时每隔五步跳转一次。
还是举之前那个例子。。。 图为： 
矩阵 \(\beta M\) 为： 
跳转矩阵为： 
所以Google矩阵 \(A\) 就是它们的和： 
进行幂迭代，结果为： 
可见，修正之后的PageRank依旧是m分最高，但也不会有蜘蛛陷阱的问题，比较完美！
实际上是如何计算PageRank的？
计算PageRank就是一个幂迭代的过程，按照公式： \(r^{new} = A \cdot r^{old}\)，看似很简单。
如果我们有足够的内存来装下 \(A, r^{old}, r^{new}\) 的话确实很简单，我们来算一下到底够不够。
假设有 \(N = 1 × 10^{9}\) 个网页，存每个网页只需要4个字节，即只存一个节点ID，那么存储地址+ID就需要 2 billion * 4 byte，约等于8GB
如果要存储矩阵A，需要存储 \(N^2\) 个地址+ID，大概需要 \(10^{18}\) 字节这个数量级的内存空间，显然是没有那么大的！
我们考虑矩阵 \(M\) 的值的分布， 如果 $ j i $ 那么 $ M_{ij} = 1/|d_j| $ ，否则 $ M_{ij} = 0 $，实际情况是每个网页一般只有10个到100个链接，即使整个web有1 billion+ 个网页，所以矩阵 \(M\) 大部分值都为0，极少数值非0 ，所以我们可以仅存储非零值来极大地减少所需存储空间。
而矩阵 \(A\) 就不一样了，$ A = M + (1 - ) e e^T $，每个值都是非零的，因为矩阵 \(M\) 中等于0的情况在 \(A\) 中都被赋予了随机跳转到任意节点的可能性。
由于 \(A\) 不能直接放在内存里计算，而 \(M\) 可以，所以要想方设法把 \(A\) 的迭代变成 \(M\) 的迭代。
公式变形
原公式为：$ r = A r $ 其中 $A_{ij} = M_{ij} + $
把它展开： \(r_i = \sum_{j=1}^{N}A_{ij} \cdot r_j\) 
最后我们得到： > $ r = M r + []_N $
这里假设 \(M\) 中没有dead-ends，其中 \([x]_n\) 表示一个项全部为 \(x\) 的向量。
经过了这样的变形，我们在每次迭代中只需要： * 计算 $ r^{new} = M r^{old}$ * 在 \(r^{new}\) 的每一项上加上常量 $ (1-)/N$ * 如果 \(M\) 中有dead-end 的话，那么 $_i r_i^{new} < 1 $ ，我们还需要重新分配一下余下部分，使其和等于1.
最终的算法
- 输入 ： 图 \(G\) 和 参数 \(\beta\)
- \(G\) 是有向图而且可以有 spider traps 和 dead ends
- 概率参数 \(\beta\)
- 输出：Pagerank 向量 \(\vec r\)
